package DP.子序列;

import org.junit.Test;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
    思路：
        公共子序列 + 转换成要删的次数 n12-公共长
    复习：
        递增子序 靠回头遍历找max
        公共子序 靠倒着走，dp[i]拿到一个稳定对的值就行
 */
public class 只能删让字符串一样_工具公共序_583 {
    @Test
    public void test() {
        System.out.println(minDistance("sea","eat"));
    }

    public int minDistance(String word1, String word2) {
        char[] s1 = word1.toCharArray();
        char[] s2 = word2.toCharArray();
        int[][] dp = new int[s1.length][s2.length];
        //初始化起点：一方到头 注意‘前’字
        dp[0][0] = s1[0]==s2[0]?1:0;
        for (int i = 1; i < s1.length; i++) {
            dp[i][0] = s1[i]==s2[0]?1:dp[i-1][0];
        }
        for (int j = 1; j < s2.length; j++) {
            dp[0][j] = s1[0]==s2[j]?1:dp[0][j-1];
        }
        //双1起
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if(s1[i]==s2[j]){
                    //能拿到值就行，我管你从谁拿那   [(i-1,j)她自己会单独自己算的
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else {
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return s1.length+s2.length-2*dp[s1.length-1][s2.length-1];
    }
}
